#include <stdlib.h>
#include "rbtree.h"

enum {BLACK, RED};

static void rotateLeft(RBTree *rbt, RBTree **rp) {
    RBTree *right = rbt->right;
    RBTree *par = rbt->par;
    rbt->right = right->left;
    right->par = par;
    if(par) {
        if(par->left == rbt)
            par->left = right;
        else
            par->right = right;
    }else
        *rp = right;
    rbt->par = right;
    right->left = rbt;
    if(rbt->right) //origin rbt->right->left
        rbt->right->par = rbt;
}

static void rotateRight(RBTree *rbt, RBTree **rp) {
    RBTree *left = rbt->left;
    RBTree *par = rbt->par;
    rbt->left = left->right;
    left->par = par;
    if(par) {
        if(par->left == rbt)
            par->left = left;
        else
            par->right = left;
    }else 
        *rp = left;
    rbt->par = left;
    left->right = rbt;
    if(rbt->left) // origin rbt->left->right
        rbt->left->par = rbt;
}

//P red; U black; N,P,G共线
// P left node
static void insertRebuildCase5l(RBTree *gpar, RBTree **rp) {
    rotateRight(gpar, rp);
    gpar->color = RED;
    gpar->par->color = BLACK;
    if(gpar->par->par == NULL)
        *rp = gpar->par;
}
// P rihgt node
static void insertRebuildCase5r(RBTree *gpar, RBTree **rp) {
    rotateLeft(gpar, rp);
    gpar->color = RED;
    gpar->par->color = BLACK;
    if(gpar->par->par == NULL)
        *rp = gpar->par;
}


//P red; U black, N,P,G不共线
// P left node, N right node
void insertRebuildCase4l(RBTree *par, RBTree **rp) {
    rotateLeft(par, rp);
    //P new N--->par->par->par as new gpar, goto case 5
    insertRebuildCase5l(par->par->par, rp);
}
// P right node, N left node
void insertRebuildCase4r(RBTree *par, RBTree **rp) {
    rotateRight(par, rp);
    //P new N--->par->par->par as new gpar, goto case 5
    insertRebuildCase5r(par->par->par, rp);
}

static void insertRebuildCase1(RBTree *rbt, RBTree **rp);
//P,U red
static void insertRebuildCase3(RBTree *par, RBTree *uncle, RBTree *gpar, RBTree **rp) {
    par->color = BLACK;
    uncle->color = BLACK;
    gpar->color = RED;
    insertRebuildCase1(gpar, rp); //gpar as the new N goto Case1
}

//N the new branch with new node, N is RED, and 
//如果把N变为黑色， 那么N符合红黑树定义
static void insertRebuildCase1(RBTree *rbt, RBTree **rp) {
    RBTree *par, *gpar, *uncle;
    par = rbt->par;
    if(par == NULL) {
        rbt->color=BLACK;
        return;
    }
    if(par->color == BLACK)  //Case2
        return;
    gpar = par->par;
    if(gpar->left == par) {
        uncle = gpar->right;
        if(uncle && uncle->color==RED)
             insertRebuildCase3(par, uncle, gpar, rp);
        else if(rbt == par->left) ////N,P,G共线
            insertRebuildCase5l(gpar, rp);
        else
            insertRebuildCase4l(par, rp);
    }else {
        uncle = gpar->left;
        if(uncle && uncle->color==RED)
            insertRebuildCase3(par, uncle, gpar, rp);
        else if(rbt == par->right) //N,P,G共线
            insertRebuildCase5r(gpar, rp);
        else
            insertRebuildCase4r(par, rp);

    }
}

static RBTree *newRBT(int val) {
    RBTree *rbt;
    rbt = malloc(sizeof(RBTree));
    if(rbt == NULL) return NULL;
    rbt->color = RED;
    rbt->left = NULL;   
    rbt->right = NULL;
    rbt->val = val;
    return rbt;
}
//rbtree is not null
static int rBTInsertCase1(RBTree *rbt, int val, RBTree **rp){
    if(rbt->val > val) {
        if(rbt->left) return rBTInsertCase1(rbt->left, val, rp);
        rbt->left = newRBT(val);
        if(!rbt->left) return -1;
        rbt->left->par = rbt;
        insertRebuildCase1(rbt->left, rp);
    }else if(rbt->val == val)
        return 1;
    else {
        if(rbt->right) return rBTInsertCase1(rbt->right, val, rp);
        rbt->right = newRBT(val);
        if(!rbt->right) return -1;
        rbt->right->par = rbt;
        insertRebuildCase1(rbt->right, rp);
    }
    return 0;
}

/**************
 * 0: inster ok
 * 1: has inserted
 * -1: mem is not enough
 *************/
int rBTInsert(RBTree **rp, int val) {
    if(*rp) // the rbtree is not null 
        return rBTInsertCase1(*rp, val, rp);
    *rp = newRBT(val);
    if(*rp == NULL) return -1;
    (*rp)->par = NULL;
    (*rp)->color = BLACK;
    return 0;
}


static void flipColor(RBTree *p1, RBTree *p2) {
    int color;
    color = p1->color;
    p1->color = p2->color;
    p2->color = color;
}


//P点颜色任意，S点是黑色
// N left node; SR red
static void deleteRebuildCase6l(RBTree *par, RBTree *sib, RBTree **rp) {
    rotateLeft(par, rp);
    flipColor(par, sib);
    sib->right->color = BLACK;
}
// N right node; SL red
static void deleteRebuildCase6r(RBTree *par, RBTree *sib, RBTree **rp) {
    rotateRight(par, rp);
    flipColor(par, sib);
    sib->left->color = BLACK;
}


//P点颜色任意，S点是黑色，
// N left node; SL red; SR black
static void deleteRebuildCase5l(RBTree *par, RBTree *sib, RBTree **rp) {
    rotateRight(sib, rp);
    sib->color = RED;
    par->right->color = BLACK;
    deleteRebuildCase6l(par, par->right, rp);
}
// N right node; SR red; SL black
static void deleteRebuildCase5r(RBTree *par, RBTree *sib, RBTree **rp) {
    rotateLeft(sib, rp);
    sib->color = RED;
    par->left->color = BLACK; //par->left new S
    deleteRebuildCase6r(par, par->left, rp);
}


/*************************************************
 * Case4: P red; S,SC both black; SC may nil
   交换P和S的颜色即可 
   Case3: P,S,SC both black; SC may nil
   把S改成红色，将P看作新的N分支调整到Case1
****************************************/

static void deleteRebuildCase1(RBTree *rbt, RBTree *par, RBTree **rp);

//S black --> P not nil
// N left node
static void deleteRebuildCase3456l(RBTree *par, RBTree *sib, RBTree **rp) {
    if(sib->right && sib->right->color==RED)
        deleteRebuildCase6l(par, sib, rp);
    else if(sib->left && sib->left->color==RED)
        deleteRebuildCase5l(par, sib, rp);   
    else { //Case34
        sib->color = RED;
        if(par->color==RED) //Case4
            par->color = BLACK;
        else
            deleteRebuildCase1(par, par->par, rp);
    }
}
// N right node
static void deleteRebuildCase3456r(RBTree *par, RBTree *sib, RBTree **rp) {
    if(sib->left && sib->left->color==RED)
        deleteRebuildCase6r(par, sib, rp);
    else if(sib->right && sib->right->color==RED)
        deleteRebuildCase5r(par, sib, rp);   
    else { //Case34
        sib->color = RED;
        if(par->color==RED) //Case4
            par->color = BLACK;
        else
            deleteRebuildCase1(par, par->par, rp);
    }
}

//S red --> P black transform to  P red, S black
// N left node
static void deleteRebuildCase2l(RBTree *par, RBTree *sib, RBTree **rp) {
    RBTree *ns; //ns
    rotateLeft(par, rp);
    sib->color = BLACK;
    par->color = RED;
    ns = par->right;
    if(ns->right && ns->right->color==RED)
        deleteRebuildCase6l(par, ns, rp);
    else if(ns->left && ns->left->color==RED)
        deleteRebuildCase5l(par, ns, rp);
    else {//Case4
        par->color = BLACK;
        ns->color = RED;   
    }
}
//N is right node
static void deleteRebuildCase2r(RBTree *par, RBTree *sib, RBTree **rp) {
    RBTree *ns; //ns
    rotateRight(par, rp);
    sib->color = BLACK;
    par->color = RED;
    ns = par->left;
    if(ns->left && ns->left->color==RED)
        deleteRebuildCase6r(par, ns, rp);
    else if(ns->right && ns->right->color==RED)
        deleteRebuildCase5r(par, ns, rp);   
    else { //Case4
        par->color = BLACK;
        ns->color = RED;
    }
}

//N less a black node, N 本身满足红黑树定义, N may nil --> P,S not nil
static void deleteRebuildCase1(RBTree *rbt, RBTree *par, RBTree **rp) {
    RBTree *sib;
    if(par == NULL) return; 
    if(par->left==rbt) {
        sib = par->right;
        if(sib->color == RED) //sib is red
            deleteRebuildCase2l(par, sib, rp); 
        else
            deleteRebuildCase3456l(par, sib, rp);
    }else {
        sib = par->left;
        if(sib->color == RED) //sib is red
            deleteRebuildCase2r(par, sib, rp); 
        else
            deleteRebuildCase3456r(par, sib, rp);
    }
}

static RBTree *findPre(RBTree *rbt) {
    rbt = rbt->left;
    while(rbt->right)
        rbt = rbt->right;
    return rbt;
}

static void doDelete(RBTree *dp, RBTree **rp) {
    RBTree  *par, *np, *prep;
    if(dp->left && dp->right) {
        prep = findPre(dp);
        dp->val = prep->val;
        dp = prep;
    } 
    if(dp->left) {
        np = dp->left;
    }else if(dp->right) {
        np = dp->right;
    }else
        np = NULL;
    par = dp->par;
    if(par) {
        if(par->left == dp)
            par->left = np;
        else 
            par->right = np;
    }else { //dp is root
        *rp = np;
    }
    if(np) np->par = par;
    //rebuild
    if(dp->color == BLACK) {
        if(np) np->color = BLACK;
        else deleteRebuildCase1(np, par, rp); 
    }
    free(dp);
}


static int rBTDeleteCore(RBTree *rbt, int val, RBTree **rp) {
    if(rbt == NULL) return -1;
    if(rbt->val > val)
        return rBTDeleteCore(rbt->left, val, rp);
    else if(rbt->val == val) { 
        doDelete(rbt, rp);
        return 0;
    }else
        return rBTDeleteCore(rbt->right, val, rp);

}
//-1: not find the val
//0: del ok
int rBTDelete(RBTree **rp, int val) {
    return rBTDeleteCore(*rp, val, rp);
}

//0: find
//-1: not find
int rBTSearch(RBTree *rbt, int val) {
    if(rbt == NULL) return -1;
    if(rbt->val > val) return rBTSearch(rbt->left, val);
    if(rbt->val == val) return 0;
    return rBTSearch(rbt->right, val);
}


#ifdef RBTTEST

#include <stdio.h>
#include<sys/time.h>
#include <stdlib.h>
#ifndef RBTSIZE
#define RBTSIZE 8
#endif //RBTSIZE

typedef struct timeval TimeVal;

void static middleOrderTraversal(RBTree *rbt) {
    if(rbt == NULL) return;
    middleOrderTraversal(rbt->left);
    printf("node: %d\n", rbt->val);
    middleOrderTraversal(rbt->right);
}

void prepareRBT(RBTree **rp, int n) {
    int i;
    for(i=0; i<n; i++)
        rBTInsert(rp, i);
}

void iSwap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}
void n_trCore(int a[], int *s, int n, int d, RBTree **rp) {
    int i, r;
    if(d == n) {
        printf("###################\n");
        for(i=0; i<n; i++)  {
            r = rBTDelete(rp, s[i]);
            printf("delete: %d, res: %d\n", s[i], r);
        }
        prepareRBT(rp, n);       
        return;
    }
    for(i=0; i<n-d; i++) {
        s[d] = a[i];
        iSwap(a+i, a+n-d-1);
        n_trCore(a, s, n, d+1, rp);
        iSwap(a+i, a+n-d-1);
    }
}


int main(void) {
    int i;
    RBTree *root = NULL;
    int r, n;
    TimeVal start, end;
    float timer;
    int a[RBTSIZE];
    int stack[RBTSIZE];
    for(i=0; i<RBTSIZE; i++)
        a[i] = i;
    
    gettimeofday(&start, NULL);
    srand(start.tv_usec);
    for(i=0; i<RBTSIZE; i++) {
        r = rBTInsert(&root, i);
        printf("insert: %d, res: %d\n", i, r);
        n = rand()%RBTSIZE;
        r = rBTSearch(root, n);
        printf("search: %d, res: %d\n", n, r);
    }
#ifdef TRDEL
    n_trCore(a, stack, RBTSIZE, 0, &root);
#endif //TRDEL
    middleOrderTraversal(root);
    for(i=RBTSIZE-1; i>=0; i--) {
        n = rand()%RBTSIZE;
        r = rBTDelete(&root, n);
        printf("delete: %d, res: %d\n", n, r);
    }
    gettimeofday(&end, NULL);
    timer = end.tv_sec - start.tv_sec + (end.tv_usec - start.tv_usec)/1000000.0;
    printf("timer = %6f seconds\n", timer);
    return 0;
}

#endif //RBTTEST
